from typing import List


# leeetcode198
# 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上
# 被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
#
#  示例 1：
# 输入：[1,2,3,1]
# 输出：4
# 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
#
#  示例 2：
# 输入：[2,7,9,3,1]
# 输出：12
# 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。
class Solution1:
    def rob2(self, nums: List[int]) -> int:
        """
        动态规划2：
        dp[i] = m 表示对前i个房屋行窃能获得的最大收益为m
        对前i个房屋行窃能获得的最大收益取决于 对前 (i - 1) 和前 (i - 2) 个房屋行窃能获得的最大收益(是否应该选择对第i个房屋行窃)
            要选择第i个房间才能获得最大收益:对前(i - 2)个房屋进行盗窃获得的最大收益 + 对第i个房间行窃的收益 >  对前(i - 1)个房屋进行盗窃获得的最大收益
            否则不应该对第i个房屋行窃
        :param nums:
        :return:
        """
        size = len(nums)
        if size == 1:
            return nums[0]
        elif size == 2:
            return max(nums)
        # dp = [0] * (size + 1)
        # dp[0], dp[1], dp[2] = 0, nums[0], max(nums[1], nums[0])
        # for i in range(3, size):
        #     # if dp[i - 2] + nums[i - 1] > dp[i - 1]:
        #     #     dp[i] = dp[i - 2] + nums[i - 1]
        #     # else:
        #     #     dp[i] = dp[i - 1]
        #     dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1])  # 上面if else的简写
        # return dp[-1]

        # 空间优化写法
        pre, dp = nums[0], max(nums[0], nums[1])
        for num in nums[2:]:
            tmp = dp
            dp, pre = max(pre + num, dp), tmp
        return dp

    def rob1(self, nums: List[int]) -> int:
        """
        动态规划1:
        在第i个房间时有两种选择状态(偷/不偷该房间)
        遍历整个nums分别记录下偷/不偷该房间的最大收益
        :param nums:
        :return:
        """
        # dpNoRob = [0] * len(nums)  # dpNoRob[i] = m 代表在前i个屋子行窃, 但不偷第i个房间能获得的最大利润
        # dpRob = [0] * len(nums)    # dpRob[i] = m 代表在前i个屋子行窃，且偷第i个房间能获得的最大利润
        # dpRob[0] = nums[0]
        # for i in range(1, len(nums)):
        #     dpNoRob[i] = max(dpRob[:i])  # 在前i - 1个屋子行窃，能获得的最大利润
        #     dpRob[i] = dpNoRob[i - 1] + nums[i]
        # return max(dpNoRob[-1], dpRob[-1])

        # 空间优化
        dpNoRob, dpRob = 0, nums[0]
        for i in range(1, len(nums)):
            tmp = dpNoRob
            dpNoRob, dpRob = max(dpNoRob, dpRob), tmp + nums[i]
        return max(dpRob, dpNoRob)

    def rob(self, nums: List[int]) -> int:
        return self.rob1(nums)


# leetcode213
# 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的
# 房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
#  给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
#
#  示例 1：
# 输入：nums = [2,3,2]
# 输出：3
# 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
#
#  示例 2：
# 输入：nums = [1,2,3,1]
# 输出：4
# 解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4 。
#
#  示例 3：
# 输入：nums = [1,2,3]
# 输出：3
class Solution2:
    def rob(self, nums: List[int]) -> int:
        """
        动态规划：和LeetCode198类似
        dp[i] = m 表示对前i个房屋行窃能获得的最大收益为m
        对前i个房屋行窃能获得的最大收益取决于 对前 (i - 1) 和前 (i - 2) 个房屋行窃能获得的最大收益(是否应该选择对第i个房屋行窃)
            要选择第i个房间才能获得最大收益:对前(i - 2)个房屋进行盗窃获得的最大收益 + 对第i个房间行窃的收益 >  对前(i - 1)个房屋进行盗窃获得的最大收益
            否则不应该对第i个房屋行窃
        由于是环形，所以要第一个房间和最后一个房间是互斥的(二者只能选其一)，所以需要计算两次，取其中大的为结果即可
        :param nums:
        :return:
        """
        size = len(nums)
        if size == 1:
            return nums[0]
        elif size == 2:
            return max(nums)
        # # 偷第一个房间(最后一个房间一定不能偷)的结果
        # dp = [0] * (size + 1)
        # dp[0], dp[1], dp[2] = 0, nums[0], max(nums[1], nums[0])
        # for i in range(3, size):
        #     dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1])
        # tmpRes = dp[-2]
        # # 不偷第一个房间(最后一个房间可能会偷)的结果
        # dp[0], dp[1], dp[2] = 0, 0, nums[1]
        # for i in range(3, size + 1):
        #     dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1])
        # return max(tmpRes, dp[-1])

        # 空间优化写法
        # 偷第一个房间(最后一个房间一定不能偷)的结果
        pre, dp = nums[0], 0
        for num in nums[2:size - 1]:
            tmp = dp
            dp, pre = max(pre + num, dp), tmp
        # 不偷第一个房间(最后一个房间可能会偷)的结果
        pre2, dp2 = 0, nums[1]
        for num in nums[2:]:
            tmp = dp2
            dp2, pre2 = max(pre2 + num, dp2), tmp
        return max(dp, dp2)


if __name__ == "__main__":
    nums = [1, 2, 3, 1]
    nums = [2, 7, 9, 3, 1]
    nums = [2, 1, 1, 2]
    print(Solution1().rob(nums))

    nums = [2, 3, 2]
    nums = [1, 2, 3]
    nums = [1, 2, 3, 1]
    print(Solution2().rob(nums))

